/*
 * heap_main.cc
 *
 *  Created on: Dec 27, 2010
 *      Author: fify
 */

#include <cstdio>

const int MAX = 1100005;

int Num[MAX];		// 原始数据

struct Heap
{
	int v;
	int off;	// 堆元素在数组a[]中的下标
};

Heap max_heap[MAX];
Heap min_heap[MAX];

int max_loc[MAX];	// 数组a[i]在max_heap中的下标
int min_loc[MAX];	// 数组a[i]在min_heap中的下标

// Results:
int Max[MAX];
int Min[MAX];

// From root node to the lowest level.
void adjust(Heap h[], int s, int n, int loc[], int isMax)
{
	int now = s;
	Heap rc = h[s];
	for(int j = (now<<1);j<=n;j <<= 1)
	{
		if(isMax)
		{
			if(j < n)
			{
				j = h[j].v > h[j+1].v ? j: j + 1;
			}
			if(rc.v > h[j].v)
				break; // Found the first smaller one.

			// Push smaller one down and move h[j] up.
			h[now] = h[j];
			loc[h[j].off] = now;
			now = j;
		}
		else
		{
			if(j < n)
			{
				j = h[j].v < h[j+1].v ? j : j + 1;
			}
			if(rc.v < h[j].v)
				break;	// Found the first larger one.

			h[now] = h[j];
			loc[h[j].off] = now;
			now = j;
		}
	}

	h[now] = rc;
	loc[rc.off] = now;
}

void make_heap(Heap h[], int n, int loc[], int isMax)
{
	for(int i = (n >> 1);i>0;--i)
	{
		adjust(h, i, n, loc, isMax);
	}
}

void solve(int n, int k)
{
	for(int i = 1;i<=n;i++)
	{
		scanf("%d", &Num[i]);
	}

	for(int i = 1;i<=k;++i)
	{
		max_heap[i].v = min_heap[i].v = Num[i];
		max_heap[i].off = min_heap[i].off = i;
		max_loc[i] = min_loc[i] = i;
	}

	make_heap(max_heap, k, max_loc, 1);
	make_heap(min_heap, k, min_loc, 0);

	Max[0] = max_heap[1].v;
	Min[0] = min_heap[1].v;

	int now;

	for(int i = k+1;i<=n;++i)
	{
		now = max_loc[i - k];
		max_heap[now].v = Num[i];
		max_heap[now].off = i;
		max_loc[i] = now;

		// Find the parent node.
		int j = now > (k>>1) ? (now >> 1) : now;

		for(;j>0;j >>= 1)
		{
			adjust(max_heap, j, k, max_loc, 1);
		}

		now = min_loc[i - k];
		min_heap[now].v = Num[i];
		min_heap[now].off = i;
		min_loc[i] = now;

		j = now > (k>>1) ? (now >> 1) : now;
		for(;j>0;j >>= 1)
		{
			adjust(min_heap, j, k, min_loc, 0);
		}

		Max[i-k] = max_heap[1].v;
		Min[i-k] = min_heap[1].v;
	}

	for(int i = 0;i<n - k + 1;++i)
		printf("%d%c", Min[i], i<n-k ? ' ' : '\n');
	for(int i = 0;i<n - k + 1;++i)
		printf("%d%c", Max[i], i<n-k ? ' ' : '\n');
}
int main()
{
	//freopen("data.in", "r", stdin);
	int n, k;
	scanf("%d%d", &n, &k);

	k = k < n ? k : n;

	solve(n, k);

	return 0;
}
